﻿using System;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Knapsack
{
    public class SpaceSavingKnapsackSolver3 : IKnapsackSolver
    {
        public double Profit(int W, IList<double> values, IList<int> weights)
        {
            var N = values.Count;
            var B = new double[W + 1];

            for (int n = 1; n <= N; n++)
            {
                for (int c = W; c >= weights[n - 1]; c--)
                {
                    B[c] = Math.Max(B[c], B[c - weights[n - 1]] + values[n - 1]);
                }
            }
            return B[W];
        }
    }
}
